'''
This is a python library of Interval Tree. Complete by Zhengbo Wang.

'''
from RBTree_utils import *

class IntervalNode(RBNode):
    def __init__(self):
        super().__init__()
        self.int = None  # 用有序数对 [low, high] 储存
        self.key = None if self.int == None else self.int[0]
        self.val = self.key # 按照 key 值做红黑树排序
        self.max = None  # max(x) = max(high(int(x)), max(left(x)), max(right(x)))     
    
    def low(self):
        return self.int[0] if self.int != None else None
    
    def high(self):
        return self.int[1] if self.int != None else None
    

class IntervalTree(RBTree):
    def __init__(self):
        super().__init__()
        self.__nil = self._RBTree__nil
        self.root = IntervalNode()
        self.root.left = self.__nil
        self.root.right = self.__nil
        
    def IntervalInsert(self, node):
        '''
        算法步骤：
        0. 查看是否有重叠
        1. 按照红黑树方法插入节点 z.
        2. 更新 z 节点及其祖先节点的 max 参数.
        '''
        z = node
        flag = self.IntervalSearch(z)
        if flag == None:
            self.insert(z)
            self.__update_max(z)
            return True
        else:
            return False
    
    def __update_max(self, z):
        '''
        更新 z 和 z 的祖先的 max 信息.
        '''
        z.max = self.__max(z)
        if z.parent != None:
            self.__update_max(z.parent)
    
    def __max(self, z):
        '''
        计算 z 节点的 max.
        '''
        if z == self.__nil:
            # 返回标记
            return None
        a = z.high()
        b = self.__max(z.left)
        c = self.__max(z.right)
        if b == None and c == None:
            return a
        elif b != None and c == None:
            return max(a,b)
        elif b == None and c != None:
            return max(a,c)
        elif b != None and c != None:
            return max(a,b,c)
    
    def IntervalDelete(self, num):
        '''
        算法步骤:
        1. 按照红黑树方法删除节点
        2. 更新被删除节点的祖先的 max 信息
        '''
        z = self.search(num)
        self.delete(num)
        if z.parent != None:
            self.__update_max(z.parent)
    
    def IntervalSearch(self, node):
        '''
        算法步骤：
        1. 从根节点开始查找. x = self.root
        2. 如果 node != nil 且于 x 不重叠.
        3. 如果左子树的 max > low(node), 那么去左子树中查找，否则去右子树中查找.
        4. 返回 x, x == None or x 和 i 重叠.
        '''
        i = node
        x = self.root 
        while x != self.__nil:
            if x.low() >= i.high() or x.high() <= i.low():
                # 不重叠
                if x.left != self.__nil and x.left.max > i.low():
                    x = x.left
                else:
                    x = x.right
            else:
                return x
        # x == self.__nil
        return None
    
    
    
    